package com.zk.algorithm.array;

import com.zk.algorithm.Utils;
import com.zk.algorithm.annotation.Easy;
import com.zk.algorithm.annotation.LeetCodeExplore;

/**
 * @author zk
 */
@LeetCodeExplore
@Easy
public class RotateImage {

    // n * n 顺时针旋转 90 度
    //
    // [1, 2, 3, 4, 5]
    //
    // [6,   7, 8, 9,     10]
    // [11,  12,13,14,    15]
    // [16,  17,18,19,    20]
    //
    // [21,22,23,24,25]
    //
    // 几遭: n / 2 = 2.5 = 2 圈
    //
    public void rotate(int[][] matrix) {
        int n = matrix.length;

        for (int i = 0; i < n / 2; i++) {
            //   j 走到哪里停? (无需走到9，这个时候就已经完了. j < (n - 1) - i，小于号，而非小于等于)
            //
            //   ↓   ↓
            //   7,  8,  9
            //   12, 13, 14
            //   17, 18, 19
            for (int j = i; j < n - 1 - i; j++) {
                // ---------------------------------------->
                // |                   (i,j)
                // |                     X
                // |  X (n-1-j, i)
                // |
                // |
                // |
                // |
                // |
                // |                         X (j,n-1-i)
                // |    X
                // | (n-1-i, n-1-j)
                // |
                // |
                // |
                // |
                // V
                //
                // (i,j)
                //    |
                //   (j,n-1-i)
                //        |
                //     (n-1-i,n-1-j)
                //              |
                //           (n-1-j,i)
                //
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = tmp;
            }
        }
    }

    public static void main(String...args) {
        RotateImage rotateImage = new RotateImage();

        int[][] matrix = new int[][] {
                {1,2,3},
                {4,5,6},
                {7,8,9}
        };
        rotateImage.rotate(matrix);
        Utils.println(matrix);

        matrix = new int[][]{
                {5, 1, 9, 11},
                {2, 4, 8, 10},
                {13, 3, 6, 7},
                {15, 14, 12, 16}
        };
        rotateImage.rotate(matrix);
        Utils.println(matrix);
    }

}
